//
// Created by lxinp on 2022/8/30.
//

#ifndef DATASTRUCTURE_SC_HASHTABLE_H
#define DATASTRUCTURE_SC_HASHTABLE_H

#include <list>
#include "hashtable.h"


/**
 * HashTable implemented using Separate Chaining
 */
template<typename K, typename V>
class SCHashTable : public HashTable<K, V> {
private:
    // Save the trouble of scoping
    using HashTable<K, V>::elems;
    using HashTable<K, V>::size;
    using HashTable<K, V>::make_iterator;
    using HashTable<K, V>::find_prime;
    using HashTable<K, V>::should_resize;

    class SCIteratorImpl;  /* Implementation of the iterator */

public:
    // Use HashTable's iterators here
    typedef typename HashTable<K, V>::iterator iterator;

    SCHashTable(size_t tsize);
    SCHashTable(const SCHashTable<K, V>& other);
    virtual ~SCHashTable();
    const SCHashTable<K, V>& operator=(const SCHashTable<K, V>& rhs);

    // Functions inherited from HashTable
    virtual void insert(const K& key, const V& value);
    virtual void remove(const K& key);
    virtual V find(const K& key) const;
    virtual bool keyExists(const K& key) const;
    virtual void clear();
    virtual V& operator[](const K& key);

    iterator begin() const {
        return make_iterator(new SCIteratorImpl(*this, 0, false));
    }

    iterator end() const {
        return make_iterator(new SCIteratorImpl(*this, size, true));
    }

private:
    std::list<std::pair<K, V>>* table;  /* Storage of key-value pairs */
    virtual void resize_table();
};


#endif //DATASTRUCTURE_SC_HASHTABLE_H
